# -*- encoding: utf-8 -*-
'''
Filename         :5_longestPalindrome.py
Description      :
Time             :2022/08/04 08:42:15
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

class Solution:
    
    ## 超时
    def longestPalindrome(self, s: str) -> str:
        ## 滑动窗口,初始窗口1， 最大窗口 len(s)
        
        n = len(s)
        if n == 0:
            return ""
        ans = s[0]
        if n == 1:
            return ans
        
        def is_palindrome(s:str, start:int, end:int):
            while start<end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            return True
        
        for i in range(2, n+1):
            for j in range(0, n):
                st = j
                ed = i+j-1
                if ed > n-1:
                    break
                if is_palindrome(s, st, ed):
                    if len(ans)<ed-st+1:
                        ans = s[st:ed+1]
        return ans
    ## 动态规划
    def longestPalindrome1(self, s: str) -> str:
        ## 定义二维动态数组
        ## 下标i,j含义，窗口的开始和结束
        n = len(s)
        dp = [ [False for _ in range(0, n)]for _ in range(0, n)]
        ## 初始化，对角线为1
        for i in range(0, n):
            dp[i][i] = True
        ## 状态转移函数
        # 情况：  s[i]!=s[j] -> dp[i][j] = false
                # s[i]==s[j] -> 1. i==j dp[i][j]==true
                              # 2. j-i==1或者2 dp[i][j]==true
                              # 3. j-i>1  判断是dp[i+1][j-1]是否为True
        max_len = 1
        begin = 0
        ## 递推开始
        # 先枚举子串长度
        for L in range(2, n+1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                if s[i]!=s[j]:
                    dp[i][j]=False
                else:
                    if j-i+1<=3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                    # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if dp[i][j] and j-i+1>max_len:
                        max_len = j-i+1
                        begin = i
        return s[begin: begin+max_len] 
    
    def longestPalindrome2(self, s: str) -> str:
        ## 中心扩散
        pass



if __name__ == '__main__':
    Solution().longestPalindrome("babad")
       
            

